<?php
/*
 * 斐波那契系列问题的递归和动态规划
 * 【题目】
 * 给定整数N，返回斐波那契数列的第N项。
 * 【补充题目1】
 * 给定整数N，代表台阶数，一次可以跨2个或者1个台阶，返回有多少种走法。
 * 【举例】
 * N=3，可以三次都跨1个台阶；也可以先跨2个台阶，再跨1个台阶；还可以先跨1个台阶，再跨2个台阶。所以有三种走法，返回3。
 * 【补充题目2】
 * 假设农场中成熟的母牛每年只会生1头小母牛，并且永远不会死。
 * 第一年农场有1只成熟的母牛，从第二年开始，母牛开始生小母牛。每只小母牛3年之后成熟又可以生小母牛。
 * 给定整数N，求出N年后牛的数量。
 * 【补充题目3】
 * 0左边必有1的二进制字符串数量
 * 【题目描述】给定一个整数N，求由"0"字符与"1"字符组成的长度为N的所有字符串中，满足"0"字符的左边必有"1"字符的字符串数量。
 * 【举例】
 * N=1。只由"0"与"1"组成，长度为1的所有字符串："0"、"1"。只有字符串"1"满足要求，所以返回1。
 * N=2。只由"0"与"1"组成，长度为2的所有字符串为："00"、"01"、"10"、"11"。只有字符串"10"和"11"满足要求，所以返回2。
 * N=3。只由"0"与"1"组成，长度为3的所有字符串为："000"、"001"、"010"、"011"、"100"、"101"、"110"、"111"。字符串"101"、"110"、"111"满足要求，所以返回3。
 */

$obj = new Code_04_FiboProblems();
echo $obj->fibo1(20). PHP_EOL;
echo $obj->fibo2(20) . PHP_EOL;
// 楼梯问题就是fibo数列的初始值不同，其他一样



class Code_04_FiboProblems
{
    public function fibo1($n) {
		if ($n < 1) {
			return 0;
		}
		if ($n == 1 || $n == 2) {
            return 1;
        }
		return $this->fibo1($n - 1) + $this->fibo1($n - 2);
	}

    /*
     * 利用矩阵求Fibonacci数列
     * |            | = |             | * |1,1| n-2次方
     * |F(n), F(n-1)| = |F(2)=1,F(1)=1| * |1,0|
     * |            |   |             |
     *
     * 结果就是计算|1,1| 矩阵的n-2次方
     *           |1,0|
     */
    public function fibo2($n)
    {
        if ($n < 1) return 0;
        if ($n ==1 || $n == 2) return 1;
        $base = [[1, 1], [1, 0]];
        $res = $this->_matrixPower($base, $n-2);
        return $res[0][0] + $res[1][0];
    }

    /*
     * 矩阵的n次阶乘
     * 小知识：一个数的N次阶乘的O(logN)解法
     * 将阶乘数N转成二进制数，如10的75次方，N=75
     * 75的二进制 = 1001011, 从右到左计算，二进制为1的对应十进制数为1,2,8,64，只有为1的才计算到结果
     * res = pow(10,1)*pow(10,2)*pow(10,8)*pow(10,64)
     */
    protected function _matrixPower($matrix, $pow)
    {
        $res = array_fill(0, count($matrix), array_fill(0, count($matrix[0]), 0));
        for ($i = 0, $len = count($res); $i < $len; $i++) {
            $res[$i][$i] = 1;
        }
        $tmp = $matrix;
        for (; $pow != 0; $pow >>= 1) {
            if (($pow & 1) != 0) {
                $res = $this->_mulMatrix($res, $tmp);
            }
            $tmp = $this->_mulMatrix($tmp, $tmp);
        }
        return $res;
    }

    // 两个矩阵相乘
    protected function _mulMatrix($m1, $m2)
    {
        $len1 = count($m1);
        $len2 = count($m2[0]);
        $len3 = count($m2);
        $res = array_fill(0, $len1, array_fill(0, $len2, 0));
        for ($i = 0; $i < $len1; $i++) {
            for ($j = 0; $j < $len2; $j++) {
                for ($k = 0; $k < $len3; $k++) {
                    $res[$i][$j] += $m1[$i][$k] * $m2[$k][$j];
                }
            }
        }
        return $res;
    }
}